package problems.contest;

import java.util.HashMap;
import java.util.Map;

/**
 * 第 344 场周赛
 * <p>https://leetcode.cn/contest/weekly-contest-344/</p>
 *
 * @author dubulingbo, 2023/05/07, 007 12:55.
 */
public class WCT344 {
    /**
     * T1|6416. 找出不同元素数目差数组
     * <p>https://leetcode.cn/problems/find-the-distinct-difference-array/</p>
     */
    public int[] distinctDifferenceArray(int[] nums) {
        // 记录每个数出现的次数
        int[] s = new int[51];
        // 记录后缀中不同元素的个数
        int scnt = 0;
        for (int num : nums) {
            ++s[num];
            if (s[num] == 1) ++scnt;
        }

        int[] p = new int[51];
        // 记录前缀中不同元素的个数
        int pcnt = 0;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            int k = nums[i];
            --s[k];
            ++p[k];
            if (s[k] == 0) --scnt;
            if (p[k] == 1) ++pcnt;
            nums[i] = pcnt - scnt;
        }

        return nums;
    }

    /**
     * T2|6417. 频率跟踪器
     * <p>https://leetcode.cn/problems/frequency-tracker/</p>
     */
    class FrequencyTracker {
        // number -> cnt
        Map<Integer, Integer> cntMap;
        // frequent -> different number's count
        Map<Integer, Integer> freMap;

        public FrequencyTracker() {
            cntMap = new HashMap<>();
            freMap = new HashMap<>();
        }

        public void add(int number) {
            int cnt = cntMap.getOrDefault(number, 0);
            if (cnt > 0) {
                // 该数还有 cnt 个，因此个数为 cnt 的要减一
                freMap.put(cnt, freMap.getOrDefault(cnt, 0) - 1);
            }
            ++cnt;
            cntMap.put(number, cnt);
            // 出现次数为 cnt+1 的数的个数 +1
            freMap.put(cnt, freMap.getOrDefault(cnt, 0) + 1);
        }

        public void deleteOne(int number) {
            int cnt = cntMap.getOrDefault(number, 0);
            if (cnt > 0) {
                // 出现次数为 cnt 的数的个数 -1
                freMap.put(cnt, freMap.getOrDefault(cnt, 0) - 1);
                --cnt;
                cntMap.put(number, cnt);
                // 次数为 0 就不要存了
                if (cnt > 0) freMap.put(cnt, freMap.getOrDefault(cnt, 0) + 1);
            }
        }

        public boolean hasFrequency(int frequency) {
            return freMap.getOrDefault(frequency, 0) > 0;
        }
    }

    /**
     * T3|6418. 有相同颜色的相邻元素数目
     * <p>https://leetcode.cn/problems/number-of-adjacent-elements-with-the-same-color/</p>
     */
    public int[] colorTheArray(int n, int[][] queries) {
        int[] c = new int[n];
        int len = queries.length;
        int[] ret = new int[len];
        int cnt = 0;

        for (int i = 0; i < len; ++i) {
            int k = queries[i][0];
            if (c[k] > 0) {
                // 原来有着色，判断左右相邻的连个格子，
                // 如果颜色相同，则减一
                if (k > 0 && c[k - 1] == c[k]) --cnt;
                if (k < n - 1 && c[k] == c[k + 1]) --cnt;
            }
            // 重新着色
            c[k] = queries[i][1];
            // 如果与相邻的格子相同，则加一
            if (k > 0 && c[k - 1] == c[k]) ++cnt;
            if (k < n - 1 && c[k] == c[k + 1]) ++cnt;

            ret[i] = cnt;
        }

        return ret;
    }

    /**
     * T4|6419. 使二叉树所有路径值相等的最小代价
     * <p>https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/</p>
     */
    public int minIncrements(int n, int[] cost) {
        int ret = 0;
        for (int p = (n - 1) / 2; p >= 0; --p) {
            ret += Math.abs(cost[2 * p] - cost[2 * p + 1]);
            // 把最大的加到父亲节点
            cost[p] += Math.max(cost[2 * p], cost[2 * p + 1]);
        }

        return ret;
    }
}
